package Hot100;

import java.util.ArrayDeque;
import java.util.Deque;

public class 滑动窗口最大值 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] maxNums = new int[nums.length - k + 1];
        Deque<Integer> deque = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            if (i >= k && nums[i - k] == deque.getFirst()) deque.pollFirst();
            if (deque.isEmpty()) deque.offerLast(nums[i]);
            else {
                while (!deque.isEmpty() && nums[i] > deque.getLast()) deque.pollLast();
                deque.offerLast(nums[i]);
            }
            if (i >= k - 1) maxNums[i - k + 1] = deque.getFirst();
        }
        return maxNums;
    }
}
